//修剪二叉搜索树
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) 
    {
        if(root==nullptr) return nullptr;
        while (root!= nullptr && (root->val<low||root->val > high)) 
        {
            if (root->val < low) root = root->right; // 小于L往右走
            else root = root->left; // 大于R往左走
        }
        TreeNode* cur=root;
        while(cur)
        {
            while(cur->left && cur->left->val < low)
            {
                cur->left=cur->left->right;
            }
           cur=cur->left;
        }
        cur=root;
        while(cur)
        {
            while(cur->right && cur->right->val > high)
            {
                cur->right=cur->right->left;
            }
           cur=cur->right;
        }
        return root;
    }
};
//删除二叉搜索树中的节点
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) 
    {
        TreeNode*cur=root;
        TreeNode* pre=nullptr;
        while(cur)
        {
            if(cur->val < key)
            {
                pre=cur;
                cur=cur->right;
            }
            else if(cur->val > key)
            {
                pre=cur;
                cur=cur->left;
            }
            else
            {
               if(cur->left==nullptr)
               {
                   if(cur!=root)
                   {
                       if(pre->left==cur)
                       {
                           pre->left=cur->right;
                       }
                       else
                       {
                           pre->right=cur->right;
                       }
                   }
                   else
                   {
                       root=cur->right;
                   }
                   delete cur;
                   cur=nullptr;
               }
               else if(cur->right==nullptr)
               {
                   if(cur!=root)
                   {
                       if(pre->left==cur)
                       {
                           pre->left=cur->left;
                       }
                       else
                       {
                           pre->right=cur->left;
                       }
                   }
                   else
                   {
                       root=cur->left;
                   }
                    delete cur;
                    cur=nullptr;
               }
               else
               {
                   TreeNode* parent_min=cur;
                   TreeNode* minNode=cur->right;
                   while(minNode->left)
                   {
                       parent_min=minNode;
                       minNode=minNode->left;
                   }
                   swap(cur->val,minNode->val);
                   if(minNode==parent_min->left)
                   {
                       parent_min->left=minNode->right;
                   }
                   else
                   {
                       parent_min->right=minNode->right;
                   }
                    delete  minNode;
                    cur=nullptr;
               }
            }
        }
        return root;
    }
};